package tests;

import java.util.Scanner;

public class test10 {
    public static void main(String[] args) {
        int[] arr = new int[10001];
        arr[1] = 1;
        arr[2] = 2;
        for(int i = 3;i < 10001;i++){
            arr[i] = arr[i-1]+arr[i-2];
            arr[i] = arr[i]%10000;
        }
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            StringBuilder sb = new StringBuilder();
            int n = sc.nextInt();
            for(int i = 0;i < n;i++){
                int xi = sc.nextInt();
                sb.append(String.format("%04d",arr[xi]));
            }
            System.out.println(sb);
        }
    }
}
